Navigation systems are used by people and vehicles for routing and directions in order to correctly and efficiently travel between two locations. Navigation systems may use link and node routing graphs for storing data and calculating routes. For a roadway network, a link and node routing graph is straightforward. A roadway network may be represented as a link node system with roads represented as links and endpoints represented as nodes. To generate a routing graph, a system simply includes those road links that are considered navigable.
Computing a routing graph for an open space, however, is not as trivial. There may not be natural nodes or links such as in a road network. An open space may not have a set pathway or track to follow. Routes may be created using a mesh that fills the open space. One implementation uses a triangulation algorithm (e.g., Delaunay triangulation) to create a mesh that fills the space with triangles from a set of calculated points. Using a mesh to generate links and nodes, however, generates jagged or confusing segments. Other methods may use line of sight between a starting point and a destination. This technique creates un-natural and jagged pathways that may be confusing to users. Users require a system that is not only direct as possible, but also capable of being understood; a navigational system which generates natural efficient turn-by-turn guidance for open spaces.